This disclosure relates generally to data decoding, and more particularly to iterative decoders for data encoded with a low-density parity check (LDPC) encoder.
With the continuing demand for high-reliability transmission of information in digital communication and storage systems, and with the rapid increase in available computational power, various coding and decoding techniques have been investigated and applied to increase the performance of these systems. One such coding technique, low-density parity check (LDPC) coding, was first proposed in the 1960s, but was not generally used until the 1990s when researchers began to investigate iterative coding and decoding techniques.
LDPC codes are among the few known error control coding techniques capable of transmitting information at a rate close to the Shannon limit or channel-capacity. LDPC codes may be used in the transmission of information on media, or channels. LDPC coding techniques are generally iterative in nature, and may be represented by many different types of parity check matrices. The structure of an LDPC code's parity check matrix may be, for example, random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as quasi-cyclic low density parity check (QC-LDPC) codes.
A LDPC decoder may decode LDPC codes using an iterative message passing algorithm, such as a min-sum decoding algorithm. Such algorithms may decode a received vector from a communication channel using an iterative process in which each iteration includes two update steps.
Some communications channels may make bit-strings of information transmitted through them have undesirable insertions or deletions. For example, patterned-media recording channels are one such type of communication channels. In such channels, undesirable insertions or deletions may occur. For example, insertions or deletions may occur when the velocity of a recording device is different than that of a reading device for patterned-media. As an illustrative example, a bit-string “0010111001110101100” may be transmitted on such a channel. The bit-string may suffer from an insertion or a deletion while being transmitted through the communication channel. The received bit-string may have an inserted bit (an insertion). For example, a bit may have been inserted after the 7th bit in the originally transmitted bit-string. Therefore, the received bit-string may be “00101111001110101100.” The received bit-string may have a deleted bit (a deletion). For example, the 13th bit in the originally transmitted bit-string may be deleted. Therefore, the received bit-string may be “001011100111101100.” Such insertions or deletions may disadvantageously lead to degraded application performance for applications utilizing the communications channel. Such insertions or deletions may also lead to lowered data transmission rates.
LDPC codes may be used to transmit information in communication channels that are prone to bit insertions or deletions. LDPC codes may be used to determine the locations of insertions or deletions in bit-strings of information transmitted through such channels. Once the locations of such insertions or deletions are known, a LDPC decoder may be preemptively notified of the locations prior to the start of the LDPC decoding process. This knowledge of the locations of insertions or deletions may help avoid errors in the decoding process brought about by the insertions or deletions. Therefore, it would be desirable to provide systems and methods which use LDPC codes to determine the locations of insertions or deletions within bit-strings of information transmitted through communication channels and which notify a LDPC decoder of the locations of the insertions or deletions prior to the start of the decoding process. Such systems and methods may lead fewer errors in the decoding process, which may improve application performance for applications utilizing the communication channel. Such systems and methods may also lead to larger data transmission rates.